package leetcode.median;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author liyifan
 * @Description 括号生成
 * @Date 13:29 2022/7/11
 * @Param
 * @return
 **/
public class $22_GenerateParenthesis {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        if (n == 0) return result;

        backtrack(result, 0, n, new StringBuffer(), 0, 0);
        return result;
    }

    public void backtrack(List<String> coll, int index, int n, StringBuffer sb, int leftCount, int rightCount) {
        if (index == 2 * n) {
            coll.add(sb.toString());
            return;
        }
        if (leftCount < n) {
            sb.append('(');
            backtrack(coll, index + 1, n, sb, leftCount + 1, rightCount);
            sb.deleteCharAt(index);
        }
        if (rightCount < n && rightCount < leftCount){
            sb.append(')');
            backtrack(coll, index + 1, n, sb, leftCount, rightCount + 1);
            sb.deleteCharAt(index);
        }
    }
}
